6 スキャナの最適化


デバッグをしている間はスキャナの性能というものは通常それほど重要ではなく、Flex のデフォルトの設定で十分です。しかしデバッグ終了後は、スピードもしくはサイズの面でスキャナを最適化したくなることもあるでしょう。ここでは、スキャナを最適化するのによく使われる手法をいくつか紹介します。

6.1 スピードの最適化

多くのプログラムは字句解析の処理に多くの時間を費やします。したがって、スキャナの最適化はかなり大きな性能改善に結びつくことが多いのです。Flex によるスキャナは Lex によるスキャナと比較するとかなり高速になる傾向がありますが、特定の構成もしくはアクションによって、性能に大きな影響を与えることができます。注意すべき点は以下のとおりです。

  1. テーブルの圧縮
  2. どのような圧縮も結果的にスキャナの性能を悪くします。したがって、スピードのことが心配であるならば、常にコマンドラインで -f オプションもしくは -F オプションを使ってください。テーブルの圧縮およびスピードに関連するオプションに関する詳細な議論については、***ページの 5.3 節「テーブルの圧縮とスキャナのスピード」を参照してください。
     

  3. REJECT
  4. これはスピードに対して最も大きな影響を及ぼすもので、これが使われるとすべてのマッチ処理が遅くなります。というのは、スキャナはマッチする前の状態に自身を復旧する必要があるからで、このようなことが必要ない場合と比較して、より多くの内部的な保守作業を行わなければならないからです。スピードが重要な場合には、これを使わないようにしてください。
     

  5. バックトラッキング(backtracking)
  6. スキャナがあるテキストにマッチするために「逆行」しなければならないことを、バックトラッキングといいます。これはスキャナの性能に悪い影響を及ぼしますので、スピードが最も重要である場合には避けるべきものです。圧縮されたテーブルは常にバックトラッキングを発生させるので、-f オプションもしくは -F オプションを使わない場合は、ルールからバックトラッキングを削除しようとするのは時間の無駄です。スキャナからバックトラッキングを削除することに関するより詳細な情報については、***ページの 6.1.1 節「バックトラッキング(backtracking)の削除」を参照してください。
     

  7. 可変長後続コンテキスト(trailing context)
  8. 可変長後続コンテキストとは、あるルールの先頭部分と末尾部分の両方が固定長でないような場合を指します。これは、性能の観点からは REJECT と同じくらい悪影響を持つもので、可能な場合にはいつでも避けるべきです。この例を示すと、以下のようになります。
     

      %%
      linux|hurd/(OS|"Operating system")
       
    これは、以下のように分割すべきです。
     
      linux/OS|"Operating system"
      hurd/OS|"Operating system"
       
    こうすることによって、問題は解消されます。
     
  9. 行の先頭を表わす演算子
  10. ^ 演算子は性能に不利な影響を及ぼします。スピードが最も重要な場合には、これを使わないでください。
     

  11. yymore()
  12. yymore を使うと性能を劣化させます。スピードが最も重要な場合には、これを使わないでください。
     

  13. テキスト長
  14. スキャナの性能は、それがマッチするテキストの長さによっても影響を受けます。常に長い文字列にマッチするような場合には、スキャナは高速に実行されます。というのは yytext 環境をセットアップする必要がないからです。ほとんどの時間は、内部の高速なマッチング・ループの中で費やされることになります。
     

  15. NUL
  16. Flex は NUL を含むトークンをマッチするのに時間がかかります。この場合には、短かいテキストにマッチするようルールを記述するほうが良いでしょう。

6.1.1 バックトラッキング(backtracking)の削除

スキャナからバックトラッキングを削除することは、スキャナの性能にかなりの影響をもたらします。残念ながら、バックトラッキングの削除はかなり複雑な作業になる可能性があります。例えば、

にはバックトラッキングがあります。スキャナが hu をマッチし、次の文字が r ではない場合、マッチされなかったテキストを ECHO するデフォルトのルールを使って h と u を処理するために、スキャナはバックトラッキングを行わなければなりません。同じことが d と e についても適用されます(これは、何かにマッチするようスキャナが努力を継続するということがもはやできないからです。この場合、スキャナはデフォルトのルールを適用し、yytext 環境をリセットしなければなりませんが、これらはいずれも時間のかかる処理です)。

コマンドライン・オプション -b を使うことで、バックトラッキングを発生させている原因に関する情報を知ることができます。これにより、バックトラッキングに関する情報を含む lex.backtrack というファイルが生成されます。上記の例の場合は、このファイルは以下のような情報を含みます。

バックトラッキング情報はセクションに分割され、個々のセクションにおいてバックトラッキングを引き起こしている1つの状態のことが記述されています。個々のセクションの最初の行から状態番号を知ることができます。2行めからは、記述ファイルの何行めが関連しているのかを知ることができます。3行めからは、バックトラッキングを発生させた文字を知ることができます。よって、最初のブロックからは、文字 r でバックトラッキングが発生し、それは記述ファイルの2,3,4行めに関連していることを見てとることができます。最後の行は、圧縮されたテーブルは常にバックトラッキングを発生させるので、テーブル圧縮を引き起こすようなコマンドライン・オプションを使う場合にはバックトラッキングを削除しようとして時間を費やすべきではないことを思い出させるためのものです。

バックトラッキングを削除するためには、それが関与している状態をキャッチするルールを加える必要があります。これは、スキャナのスピードには影響を与えないということに注意してください。スキャナのスピードは、ルールの数や複雑さとはほぼまったく無関係です。

バックトラッキングを削除するためにルールを追加する方法には2種類あります。最初の方法は以下のようなルールを追加することです。

あるいは、すべてをキャッチするようなルールを追加することもできます。 この第2の方法は、それが適用できるような場合には常に使われるべきです。これらのいずれかと -b オプションを一緒に使うと、 というメッセージが出力されるだけです。これは、バックトラッキング状態が存在しないことを示唆しています。

これに付随する問題の1つに、複雑なスキャナではバックトラッキング問題はカスケードする傾向があるので lex.backtrack 内の情報が混乱をもたらすことがありえるということがあります。しかし、バックトラッキングの原因は通常2、3個のルールにしぼることが可能なので、バックトラック・データを調べようと努力するだけの値打ちはあります。

6.2 サイズの最適化

Flex は、サイズの小さいスキャナよりもむしろ非常に高速なスキャナを作成することを目標としていますが、いずれにしても、作成されるテーブルのサイズは Lex によるそれと比較しても通常はかなり小さいものになります。

デフォルトでは Flex は可能な限りサイズの小さいスキャナを作成します。これはコマンドラインで -Cem を使うのと同等です。デフォルトを使うのであれば、コマンドライン・オプションを気にする必要はありません。

さらにテーブルのサイズを小さくするには、より大きなテキスト・グループにマッチするルールを使い、字句の値を認識するには C のサブルーチンを使うのが最も良い方法です。この良い例がコンパイラで、そこでは以下のようなルールを与えることができます。

あるいは、以下のようにテーブル検索を使うことも可能です。 ここでは、一般的なルールが指定されていて、lookup() がテキストをキーワードにマッチさせ、そのトークンが何であるかを示す整数値を返します。これにより、サイズのより小さいテーブルが生成されますが、性能は悪くなる傾向があります。また、数が少なく複雑ではないルール集合については、テーブル・サイズを縮小することの効果は、シンボル・マッピング用の情報をプログラム中の他の領域に格納しなければならないという事実によって相殺されるかもしれません。というのは、シンボル・マッピング用の情報は、Flex テーブルと比較してより多くのスペースを必要とする可能性があるからです。


Copyright (C) 1992, 1993 Free Software Foundation

Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies.

Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one.

Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by the Free Software Foundation.


日本語訳:市川和久
Japanese translation by Kazuhisa Ichikawa (ki@home.email.ne.jp)